Módulo Redes Sociales: Sesión 3

Departamento de Estadística

Universidad Nacional de Colombia, Sede Bogotá

Equipo de trabajo

Docente del módulo

Monitor del módulo

Código a ejecutar para empezar (de clic en donde en dice “Code”, para desplegar el código, y luego copie y pegue en una sesión abierta de R):

Code
# cambia idioma de la consola de R a español:
Sys.setenv(LANG="es")
# usar 2 cifras significativas y tiende a evitar 
# notación científica (ver ayuda de función: `options`): 
options(digits = 2, scipen = 999) 
# cargar librerías: 
if(!require(igraph)){
  install.packages("igraph"); library(igraph)}
if(!require(sand)){
  install.packages("sand"); library(sand)}

Grafos y subgrafos

Grafos

Un grafo G = (V, E) es una estructura que consiste de un conjunto de vértices (nodos) V y de un conjunto de aristas (enlaces) E, donde los elementos de E son parejas de la forma e=\{u,v\}, con u,v\in V.

Subgrafos

Un grafo G'=(V',E') es un subgrafo de G=(V,E) si V'\subset V y E'\subset E.

Isomorfismo

Dos grafos que son equivalentes estructuralmente (a pesar de las etiquetas de los vértices) se denominan isomorfos.

Dos grafos G_1 = (V_1, E_1) y G_2 = (V_2, E_2) son isomorfos, lo que se escribe G_1 \equiv G_2, si existe una biyección \varphi:V_1\longrightarrow V_2 tal que \{u,v\}\in E_1 si y solo si \{\varphi(u),\varphi(v)\}\in E_2.

Ejemplo

Si G_1 \equiv G_2, entonces |V_1| = |V_2| y |E_1| = |E_2|.

Si |V_1| \neq |V_2| o |E_1| \neq |E_2|, entonces G_1 \not\equiv G_2.

Si G_1 \equiv G_2 y \{u,v\}\notin E_1, entonces \{\varphi(u),\varphi(v)\}\notin E_2.

Ejercicio

¿G_1 y G_2 son isomorfos?

Ejemplo Práctico

Creación grafos

suppressMessages(suppressWarnings(library(igraph)))

g1 <- graph_from_literal(0-1, 1-2, 2-3, 3-4, 4-0)
g2 <- graph_from_literal(a-c, a-d, b-d, b-e, c-e)

Son isomorfos?

# 'method'
# auto: Selecciona el mejor procedimiento
# direct: Si el grafo tiene tres o cuatro vértices
# vf2: Si el grafo es dirigido
# bliss: En cualquier otro caso

isomorphic(g1, g2, method = "auto")
[1] TRUE

Visualización

# visualización
set.seed(123)
par(mfrow = c(1,2))
plot(g1, vertex.size = 15, main = "Grafo 1")
plot(g2, vertex.size = 15, main = "Grafo 2")

Adyacencia

  • Vértives adyacentes

    Se dice que dos vértices u, v \in V son adyacentes (adjacent), lo que se denota con u\sim v, si u y v están conectados por alguna arista de E.

  • Vértives asilados

    Un vértice v\in V se llama asilado (isolated) si v\not\sim u para todo u\in V.

    Un grafo se puede almacenar por medio de una matriz de aristas y una lista de vértices aislados.

  • Vértices incidentes

    Un vértice v \in V es incidente (incident) en una arista e\in E si e = \{v,u\} para algún u\in V.

Grado

  • El grado (degree) del vértice v\in V se define como el número de aristas incidentes en v.

  • Para dígrafos, el grado de entrada (in-degree) y el grado de salida (out-degree) del vértice v\in V se definen como el número de aristas que apuntan hacia dentro y hacia fuera de v, respectivamente.

Ejemplo

Creación de la red no dirigida

g <- graph_from_literal(1-2, 1-3, 2-3, 2-4, 3-5, 4-5, 4-6, 4-7, 5-6, 6-7)

Vecinos del vértice 1

neighbors(graph = g, v = 1)
+ 2/7 vertices, named, from 0ab6204:
[1] 2 3

Grados

degree(graph = g)
1 2 3 4 5 6 7 
2 3 3 4 3 3 2 

Visualización

set.seed(123)
plot(g)

Ejemplo

# red dirigida
dg <- graph_from_literal(1-+2, 1-+3, 2++3)
# grado de entrada
degree(graph = dg, mode = "in")
1 2 3 
0 2 2 
# grado de salida
degree(graph = dg, mode = "out")
1 2 3 
2 1 1 
# visualización
set.seed(123)
plot(dg)

Movimiento

Caminata:

Una caminata (walk) de v_0 a v_\ell de longitud \ell es una secuencia alternante \{v_0,e_1,v_1,e_2,v_2,\ldots,v_{\ell-1},e_\ell,v_\ell\} en la que los puntos extremos de e_i son \{v_{i-1}, v_i\}, con i=1,\ldots,\ell (se pueden repetir vértices y aristas).

Ejemplo

  • 1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 3\, es una caminata abierta.
  • 1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 3\rightarrow 1\, es una caminata cerrada.

Sendero

Un sendero (trail) es una caminata abierta sin aristas repetidas (se pueden repetir vértices).

  • 1\rightarrow 3\rightarrow 8\rightarrow 6\rightarrow 3\rightarrow 2\, es un sendero.

Circuito

Un circuito (circuit) es una caminata cerrada sin aristas repetidas (se pueden repetir vértices).

  • 1\rightarrow 2\rightarrow 4\rightarrow 3\rightarrow 6\rightarrow 8\rightarrow 3\rightarrow 1\, es un circuito.

Ciclo

Un ciclo (cycle) es una caminata cerrada con al menos tres aristas no repetidas y vértices intermedios distintos.

  • 1\rightarrow 2\rightarrow 4\rightarrow 3\rightarrow 1\, es un ciclo.

Los grafos que no contienen ciclos se denominan acíclicos (acycle).

Conectividad

  • Se dice que un vértice v es accesible (reachable) desde otro vértice u si existe una caminata desde u hasta v.

  • Se dice que un grafo está conectado (connected) si cada vértice es accesible desde todos los demás.

  • Una componente (component) de un grafo es un subgrafo conectado maximalmente, i.e., un subgrafo al que añadirle cualquier otro vértice arruina la conectividad.

Ejemplo: grafos conectados con 5 vértices

Ejemplo

Creación de la red no dirigida

g <- graph_from_literal(1-7, 2-7, 2-4, 3-6, 4-7, 5-11, 6-12, 7-8, 7-9, 7-10)

Es conectado?

is_connected(g)
[1] FALSE

Componentes

clusters(g)
$membership
 1  7  2  4  3  6  5 11 12  8  9 10 
 1  1  1  1  2  2  3  3  2  1  1  1 

$csize
[1] 7 3 2

$no
[1] 3

Visualización

set.seed(123)
plot(g)

Tipo de conexión

  • Un digrafo está conectado débilmente (weakly connected) si el grafo subyacente (resultado de remover la direccionalidad) está conectado.

  • Un digrafo está conectado fuertemente (strongly connected) si cada vértice es accesible desde todos los demás mediante una caminata dirigida.

Ejemplo

Creació de la red dirigida

dg <- graph_from_literal(1-+2, 1-+3, 2++3)

Esconectado débilmente?

is_connected(graph = dg, mode = "weak")
[1] TRUE

Es conectado fuertemente?

is_connected(graph = dg, mode = "strong")
[1] FALSE

Visualización

set.seed(123)
plot(dg)

Distancia

  • La distancia geodésica entre dos vértices de un grafo es la longitud de la caminata más corta entre los vértices.

  • La distancia se define como infinito si no existen caminatas entre los vértices.

  • El valor de la distancia más grande de un grafo se llama diámetro del grafo.

  • La distancia geodésica promedio es una medida del grado de separación de los vértices.

Ejemplo

Creación de la red no dirigida

g <- graph_from_literal(1-2, 1-3, 2-3, 2-4, 3-5, 4-5, 4-6, 4-7, 5-6, 6-7)

Distancia

distances(graph = g, v = 1, to = 6)
  6
1 3

Caminata

shortest_paths(graph = g, from = 1, to = 6)$vpath
[[1]]
+ 4/7 vertices, named, from 0b2fc97:
[1] 1 2 4 6

Visualización

set.seed(123)
plot(g)

Caminatas

all_shortest_paths(graph = g, from = 1, to = 6)$res
[[1]]
+ 4/7 vertices, named, from 0b2fc97:
[1] 1 3 5 6

[[2]]
+ 4/7 vertices, named, from 0b2fc97:
[1] 1 2 4 6

Distancias

(D <- distances(graph = g, v = V(g), to = V(g)))
  1 2 3 4 5 6 7
1 0 1 1 2 2 3 3
2 1 0 1 1 2 2 2
3 1 1 0 2 1 2 3
4 2 1 2 0 1 1 1
5 2 2 1 1 0 1 2
6 3 2 2 1 1 0 1
7 3 2 3 1 2 1 0

Diámetro

diameter(g)
[1] 3

Diámetro (otra manera)

max(D[lower.tri(D)])
[1] 3

Sendero del diámetro

(d <- get_diameter(g))
+ 4/7 vertices, named, from 0b2fc97:
[1] 1 2 4 6

Visualización del diámetro

V(g)$color <- "white"
E(g)$color <- "grey"
E(g)$width <- 1
V(g)[d]$color <- "royalblue"
E(g, path = d)$color <- "royalblue"
E(g, path = d)$width <- 2
set.seed(123)
plot(g)

Distancia geodésica promedio

mean_distance(g)
[1] 1.7

Distancia geodésica promedio (otra manera)

mean(D[lower.tri(D)])
[1] 1.7

Distribución de las distancias

distance_table(g)
$res
[1] 10  8  3

$unconnected
[1] 0

Visualización

senderos <- distance_table(g)$res
names(senderos) <- 1:length(senderos)
barplot(prop.table(senderos), xlab = "Distancia geodésica", ylab = "F. Relativa", border = "grey", col = "grey", main = "Distribución de distancias geodésicas")